1. Field of the Invention
The invention relates to the data structures for representing an electronic circuit, and more particularly, the invention relates to a computer readable medium and a method of describing data structures for representing an electronic circuit as a routing-resource graph.
2. Background Information
Programmable Circuit Arrays (xe2x80x9cPCAxe2x80x9d) can be programmed to define desired routing paths. A field programmable gate array (xe2x80x9cFPGAxe2x80x9d) is a PCA comprising configurable logic elements and a programmable routing network. The routing network and logic elements exhibit a regularity, such as a tiling of a small number of different types of subcomponents creating large mosaics of regular programmable structure. A user""s design can be mapped onto an FPGA by selecting and configuring appropriate logic elements and interconnecting them, along with FPGA inputs and outputs, using the routing network and a suitable programming of the routing network which has been derived using a xe2x80x9crouter.xe2x80x9d
An exemplary routing structure has horizontal and vertical lines representing wires or metal traces within the FPGA capable of carrying signals throughout the FPGA chip. At the intersection of a horizontal and vertical line, a programmable switch xe2x80x9cxxe2x80x9d can be configured to either connect the wires represented by the underlying horizontal vertical lines (xe2x80x9cclosedxe2x80x9d) or to leave them unconnected (xe2x80x9copenxe2x80x9d). Inputs and outputs to the FPGA are represented as small squares, and configurable function units are represented as labeled rectangles. Closing appropriate switches will create an effective circuit within the FPGA, interconnecting desired inputs, outputs (i.e., squares) and functions units (i.e., rectangles). A a single xe2x80x9ccellxe2x80x9d or xe2x80x9ctilexe2x80x9d (composed of a function unit, several wire segments, and switches) can be replicated and abutted many times to create the FPGA.
To create a router that is independent of any specific FPGA architecture and usable for multiple FPGA targets, a routing-resource graph, or similar structure, is used to represent the routing network within the FPGA. As referenced herein, a xe2x80x9crouting-resource graphxe2x80x9d is any structural representation wherein a node is used to represent a wire, input, output, or pin on a logic block; a directed edge is used to represent a unidirectional switch (e.g. a programmable buffer) and a pair of directed edges are used to represent a bidirectional switch (e.g. a pass transistor). As referenced herein, a routing-resource graph can be used to represent an arbitrary routing architecture, such that a general-purpose router can configured independent of any particular FPGA architecture. After creating a routing-resource graph for a desired FPGA target, a general purpose router can route a user""s design onto the FPGA. A routing-resource graph can also map onto object-oriented programming, allowing the use of instances of a xe2x80x9cSwitchxe2x80x9d class and a xe2x80x9cWirexe2x80x9d class to represent the routing network in an FPGA.
A routing-resource graph can require large memory. For example, an FPGA can have hundreds of thousands or wires, and tens of millions of switches, and these numbers will only increase as technology advances. Representing such a current FPGA with a straightforward resource-routing graph implementation can several gigabytes or more of memory.
It is known to exploit the regularity of a routing architecture to trade-off computation for memory. For example, consider the routing of a signal from a horizontal wire H0 starting in cell (0, 0) to a desired target vertical wire Vf. From a switch table, a router can deduce that there are two switches in the current cell (0, 0) potentially connecting to vertical wires V0 and V1. By calling a first function (i.e., a first method call) for the first switch, the router finds that the first switch leads to a wire Va, and by calling the first function for the second switch, the router finds that the second switch leads to a wire Vb, neither of which is the desired target vertical wire Vf. The router proceeds along wire H0 to the next cell to the right, (1, 0), taking into account any twist in the horizontal wire bus between the two cells (0, 0) and (1, 0). In cell (1, 0), the same wire thus has the local name H1. Again by calling the first function, the router can discover that the second switch within cell (1, 0) leads to the desired target wire Vf.
A compute based approach is an effective alternative to the resource routing graph, and is used in the JRoute code supplied with the JBits system offered by Xilinx. The advantage is that much less memory is needed to represent the switched connectivity. For example, instead of the 54 instances of Switch data structures used in a typical routing-resource graph, a small switch table plus some easily written functions will suffice. Memory savings can be more dramatic in an FPGA comprising tens of thousands of cells. However, the internal structures of the FPGA have to be exposed to the router so that it can be used to navigate the routing network. A router written at this level can not be easily adapted to a different FPGA architecture.
The present invention relates to efficiently representing an electronic circuit array as a routing-resource graph using reduced memory (e.g., use of a Flyweight Design Pattern with a computation based approach).
In accordance with an exemplary embodiment of the present invention, a computer readable medium containing a computer program is provided for representing an electronic circuit, which has been segmented into plural blocks, as a routing-resource graph that includes a first wiring data structure with first switch information and a first wire identity information to identify a first wire across a first plurality of blocks, a second wiring data structure with the first switch information and a second wire identity information to identify a second wire across a second plurality of blocks, and a first switch data structure associated with the first and second wiring data structures for identifying a third wire connected to the first wire with a switch as a function of the first wire identity information and wire information from the first switch data structure.
In accordance with another exemplary embodiment of the present invention, a method for representing an electronic circuit as a routing-resource graph includes defining a plurality of blocks each having a regular sub-array of switches and wires, defining a first wiring data structure with first switch information and first wire identity information to identify a first wire, defining a second wiring data structure with first switch information and second wire identity information to identify a second wire, and defining a first switch data structure having wire information and associated with the first and second wiring data structures for identifying wires respectively connected to the first and second wires by a switch as a function of wire identity information and the wire information.